#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;

#define INFINITY 100000

//边结点
struct EdgeNode
{
    int point;//终点
    int weight;//权重
    EdgeNode *next;//指向的下一条边
};
//点结点
struct VertexNode
{
    int vertex;//起始点
    EdgeNode *edge;//指向的第一条边
};

class Graph
{
public:
    vector <VertexNode> a;//存放点节点的向量
    int vertexnum;//点数
    int edgenum;//边数
    Graph();//构造函数
    void Bellman1(int v);//Bellman-Ford算法函数
    void Bellman2(int v);//Bellman-Ford改进算法函数
};

Graph :: Graph()
{
    cout << "please input the number of vertexs and edges" <<endl;
    cin >> vertexnum >> edgenum;

    for(int i=0;i<=vertexnum;i++)
    {
        VertexNode x;
        x.vertex=i;
        x.edge=NULL;
        a.push_back(x);
    }
    
    cout << "please input the startpoint,endpoint,and weight" <<endl;
    for(int i=0;i<edgenum;i++)
    {
        int s=0,e=0,w=0;
        cin >> s >> e >> w;
        EdgeNode *x;
        x=new EdgeNode;
        x->point=e;
        x->weight=w;
        x->next=a[s].edge;
        a[s].edge=x;    
    }
}

void Graph :: Bellman1(int v)
{
    EdgeNode *temp;
    vector <int> Final;
    int flag=0;
    for(int i=0;i<=vertexnum;i++)
        Final.push_back(INFINITY);
    Final[v]=0;
    for(int i=1;i<=vertexnum;i++)
    {
        for(int j=1;j<=vertexnum;j++)
        {
            temp=a[j].edge;
            while(temp)
            {
                if(Final[temp->point] > Final[j] + temp->weight)
                {
                    Final[temp->point] = Final[j] + temp->weight;
                    if(i==vertexnum) flag=1;
                }
                temp=temp->next;
            }
        }
    }

    if(flag)
        cout << "there is a negative cycle" << endl;
    else
    {
        for(int i=1;i<=vertexnum;i++)
        {
            
            if(Final[i]>=INFINITY)
            {
                cout << "there is no way from " << v << " to " << i << endl;
            }
            else
            {
                cout << "the distance from " << v << " to " << i << " is " << Final[i]<< endl;
            }
        }
    }
}

void Graph :: Bellman2(int v)
{
    EdgeNode *temp;
    vector <int> Final,mid;
    int flag=0;
    for(int i=0;i<=vertexnum;i++)
    {
        Final.push_back(INFINITY);
        mid.push_back(0);
    }
    Final[v]=0;
    for(int i=1;i<=vertexnum;i++)
    {
        int check=0;
        for(int j=1;j<=vertexnum;j++)
            mid[j]=Final[j];
        for(int j=1;j<=vertexnum;j++)
        {
            temp=a[j].edge;
            while(temp)
            {
                if(Final[temp->point] > Final[j] + temp->weight)
                {
                    Final[temp->point] = Final[j] + temp->weight;
                    if(i==vertexnum) flag=1;
                }
                temp=temp->next;
            }
        }
        for(int j=1;j<=vertexnum;j++)
        {
            if(mid[j]!=Final[j])
            {
                check=1;
                break;
            }
        }
        if(!check) break;
    }
    
    if(flag)
        cout << "there is a negative cycle" << endl;
    else
    {
        for(int i=1;i<=vertexnum;i++)
        {
            
            if(Final[i]>=INFINITY)
            {
                cout << "there is no way from " << v << " to " << i << endl;
            }
            else
            {
                cout << "the distance from " << v << " to " << i << " is " << Final[i]<< endl;
            }
        }
    }
}

#endif